package dataStructures;

public class BSTKeyOrderIterator<K, V> implements Iterator< Entry<K, V>> {
	
	private static final long serialVersionUID = 0L;
	private BSTNode<K, V> current;
	private BSTNode<K, V> max;
	private BSTNode<K, V> aux;
	private BSTNode<K, V> root;
	private boolean end;

	Stack<BSTNode<K,V>> stack = new StackInList<BSTNode<K,V>>();
	
	public BSTKeyOrderIterator(BSTNode<K, V> node){
		root = node;
		current = node;
		max = node;
		end = true;
		while(current !=null ){
			stack.push(current);
			current = current.getLeft();
		}
		while(max.getRight()!=null)
			max = max.getRight();		
	}

	@Override
	public boolean hasNext() {
		return end;
	}

	@Override
	public EntryClass<K, V> next() throws NoSuchElementException {
		current = stack.pop();
		if(max == current){
			end = false;
			return current.getEntry();
		}
		if(current.getRight() != null){
			aux=current.getRight();
			while(aux != null){
				stack.push(aux);
				aux = aux.getLeft();
			}
		}
		if(current == max)
				end = false;					
		return current.getEntry();
	}
	
	@Override
	public void rewind() {
		stack = new StackInList<BSTNode<K,V>>();
		current = root;
		while(current!=null){
			stack.push(current);
			current = current.getLeft();
		}
	}

}
